#ifndef _CACHEMAP_HH_
#define _CACHEMAP_HH_
#include "Torus.hh"
#include "Bug.h"
#include <queue>
#include <new>
#include <algorithm>


/// Torus with reachability maps
struct CacheMap : public Torus
{
  
  /// An iterator to loop around reachable locations
  struct reach_iterator
  {
    uLocation * p_loc;
    
    reach_iterator(unsigned _offset, uLocation* _reach_map) : 
      p_loc(_reach_map+_offset)
    {
    }
    
    void operator++(void)
    {
      ++p_loc;
    }

    bool operator!=(const reach_iterator & b) const
    {
      return p_loc != b.p_loc;
    }
    
    uLocation operator*(void) const
    {
      return *p_loc;
    }
  };


  double attackRadius, viewRadius, spawnRadius;

  // precomputed list of reach positions for attack
  uLocation * _attack_reach_map;
  // size of this list
  unsigned attack_surface;

  
  reach_iterator attack_begin(uLocation loc)
  {
    ASSERT(_attack_reach_map);
    return reach_iterator(loc*attack_surface,_attack_reach_map);
  }

  reach_iterator attack_end(uLocation loc)
  {
    return reach_iterator((loc+1)*attack_surface,_attack_reach_map);
  }

  

  // precomputed list of reach positions for food gathering
  uLocation * _food_reach_map;
  // size of this list
  unsigned food_surface;
  

  reach_iterator food_begin(uLocation loc)
  {
    ASSERT(_food_reach_map);
    return reach_iterator(loc*food_surface,_food_reach_map);
  }

  reach_iterator food_end(uLocation loc)
  {
    return reach_iterator((loc+1)*food_surface,_food_reach_map);
  }


  /// Class builder
  CacheMap() : Torus(), attackRadius(0), viewRadius(0), spawnRadius(0), 
	  _attack_reach_map(NULL), attack_surface(0),
	  _food_reach_map(NULL), food_surface(0)
  { }


  /// Class initializer
  void init(unsigned _rows, unsigned _cols, 
	    double _attackRadius, double _viewRadius, double _spawnRadius)
  {
    TRACK();

    bug << "new map, (" << _rows << " x " << _cols << ')' << std::endl;
    
    Torus::init(_rows,_cols);
    attackRadius = _attackRadius;
    viewRadius = _viewRadius;
    spawnRadius = _spawnRadius;

    refresh_attack_and_spawn_reach_map();
  }

  // Class killer
  virtual ~CacheMap()
  {
    if (_attack_reach_map) delete[] _attack_reach_map;
    if (_food_reach_map) delete[] _food_reach_map;
  }

  /// used at begining and sometimes to remove water squares from reach_maps
  void refresh_attack_and_spawn_reach_map(void)
  {
    TRACK();
    init_reach_map(_attack_reach_map,attackRadius,attack_surface);
    init_reach_map(_food_reach_map,spawnRadius,food_surface);
  }

  /// compute reachable surface
  /// i.e. max number of reachable locations for a given radius
  unsigned reach_surface(double radius)
  {
    unsigned surface = 0;

    visited.reset();
    std::queue<uLocation> locQueue;
    locQueue.push(0);
    visited.insert(0);
	    
    while(!locQueue.empty())
      {
	uLocation cLoc = locQueue.front();
	locQueue.pop();
	surface++;
		
	for(unsigned d=0; d!=Torus::TDIRECTIONS; d++)
	  {
	    uLocation nLoc = getLocation(cLoc, d);
	    if(not visited.count(nLoc) and distance(0,nLoc) <= radius)
	      {
		locQueue.push(nLoc);
	      }
	    visited.insert(nLoc);
	  }
      }

    return surface;
  }

  /// init reach map
  void init_reach_map(uLocation *  & reach_map, double radius, unsigned & surface)
  {
    TRACK();
    ASSERT(reach_map==NULL);

    surface = reach_surface(radius);

    try
      {
	reach_map = new uLocation[Torus::size*surface];
      }
    catch (std::bad_alloc& ba)
      {
	bug << "bad_alloc caught: " << ba.what() << std::endl;
      }
    
    for(uLocation sLoc = 0; sLoc!=size; ++sLoc)
      {
	visited.reset();
	unsigned offset = 0;
	
	std::queue<uLocation> locQueue;
	locQueue.push(sLoc);
	visited.insert(sLoc);
	
	while(!locQueue.empty())
	  {
	    uLocation cLoc = locQueue.front();
	    locQueue.pop();
	    reach_map[sLoc*surface+offset] = cLoc;
	    offset++;
	    
	    for(unsigned d=0; d!=Torus::TDIRECTIONS; d++)
	      {
		uLocation nLoc = getLocation(cLoc, d);
		if(not visited.count(nLoc) and distance(sLoc,nLoc) <= radius)
		  {
		    locQueue.push(nLoc);
		  }
		visited.insert(nLoc);
	      }
	  }

	// Better locality
	std::sort(reach_map+sLoc*surface,reach_map+(sLoc+1)*surface);
      }
  }
};


#endif /* _CACHEMAP_HH_ */
